package tree.segmenttree;

import java.util.HashMap;
import java.util.Map;

/**
 * @Classname : MyCalendarII
 * @Description : <a href="https://leetcode.cn/problems/my-calendar-ii/">731. 我的日程安排表 II</a>
 * @Author : chentianyu
 * @Date 2023/2/18 22:17
 */


public class MyCalendarII {

    // 由于区间范围极大[0, 10^9]，创建数组会导致空间浪费，因此使用map来实现线段树
    // Integer：区间索引；  arr[0]：当前区间中最大预定次数；  arr[1]：增加内容(兼懒惰标记)
    private Map<Integer, int[]> d;
    private final int ARRAY_SIZE = 2;

    public MyCalendarII() {
        // 初始日程为空，无需初始构建线段树
        d = new HashMap<>();
    }

    public boolean book(int start, int end) {
        update(start, end - 1, 1, 0, (int)1e9, 0);
        if (d.get(0)[0] > 2) {
            update(start, end - 1, -1, 0, (int)1e9, 0);
            return false;
        }
        return true;
    }

    private void update(int l, int r, int c, int s, int t, int p) {
        int[] a = d.computeIfAbsent(p, x -> new int[ARRAY_SIZE]);
        if (l <= s && t <= r) {
            a[0] += c;
            a[1] += c;
        } else {
            int m = s + ((t - s) >> 1);
            int[] al = d.computeIfAbsent(2 * p + 1, x -> new int[ARRAY_SIZE]);
            int[] ar = d.computeIfAbsent(2 * p + 2, x -> new int[ARRAY_SIZE]);
            if (0 != a[1] && s != t) {
                al[0] += a[1];
                al[1] += a[1];
                ar[0] += a[1];
                ar[1] += a[1];
                a[1] = 0;  // 清除懒惰标记
            }
            if (l <= m) update(l, r, c, s, m, 2 * p + 1);
            if (r > m) update(l, r, c, m + 1, t, 2 * p + 2);
            a[0] = Math.max(al[0], ar[0]);
        }
    }
}
